The invention relates to a method for performing a computer assisted product configuration.
A complex product is composed of several components. A product model of a complex product is often made by looking at the product as being composed of several generic components. For each of these components there is a group of specific alternatives.
An example of a product model of a bike is: A bike is build of the following components: a frame, a front wheel, a rear wheel and a gear set. The following alternatives for the frame component exists: carbon male, standard female, standard male, off-road. For the front wheel component: slick, off-road. For the rear wheel component: slick, off-road. And, finally, for the gear component: internal three speed, external 10 speed.
In the context of configuration the word “component” is not to be understood only as the generic description of a physical component. It could also be attributes such as colour and shape, parameters such as number of gears and horsepower. A component could also be understood as “need attributes”, which express a need from the user of the configurator rather than a property of the product, such as the type of a bicycle (off-road, city bike, heavy duty bike etc.), the taste of a user (fashionable, classic, childish), or the price or weight or similar properties of interest for a user of a product.
A specific alternative must be selected for each of the components to build the complex product. A number of selections is called a partial configuration of the product. The complete selection of an alternative for each component is called a complete configuration (or just a configuration) of the product.
The number of possible configurations of the product grows rapidly with the number of components the product is composed of. For example, to configure the example bike, one must select among four frames, two front wheels, two rear wheels and two gears. Thus there exists 4×2×2×2=32 different configurations In realistic examples, this number quickly grows beyond millions.
Due to incompatibilities, etc., all combinations of the alternatives will not work. If we consider the bike example, it might be the case that the front and the rear wheel must be of the same type. Another requirement could be that the carbon male frame is the only frame allowing the external 10 speed gear. The descriptions of these incompatibilities between the alternatives are called the product requirements. The product requirements are often expressed as rules defining compatibilities between components. A configuration is said to be consistent if all requirements are satisfied. For the bike example, there are 10 different consistent configurations (8 configurations with an internal three speed gear and 2 configurations with an external 10 speed gear) out of the 32 possibilities.
In general, the requirements can be complicated and hard to overview for a human, and it is a complex task to determine a consistent configuration. A computer program can be of great help during the configuration process and generally works by checking a user's selections against the rules. This checking is generally hard to perform: either the checking may take unreasonable long time or the results of the checks may be imprecise. There are at least two different ways of treating the rules.    Explicit Enumeration This method typically uses bit-vectors to represent all possible consistent configurations. All possible configurations are tested against the rules and the configurations that turns out to be consistent are enumerated in a list, typically using a hash-table of bit-vectors. One key limit with this approach is that the number of configurations grow rapidly when the number of available components rises (typically, the number of configurations grows exponentially with the number of components). This means that the amount of memory which is required is extremely large and the method is not applicable to large product models. Another problem is that even if the number of configurations is small enough to be kept in memory, the algorithms need to traverse and treat each possible configuration independently yielding running times that are linear in the number of configurations.    Rule/Constraint Propagation When a configuration selection is made, the rule database is searched in order to check for consistency. The search time is unpredictable and therefore often limits are imposed on the allowed time consumption in order to ensure a timely response to the user. In order to meet the time limit, the search must often be ended prematurely without the full and correct result being known. The search is based on the accumulation of information by repeatedly applying the rules from the rule base to the selections that have been made. This is often very costly. Furthermore, the search time, and thus the quality of the search, is highly dependent on exactly how the rules have been formulated.
State-of-the-art tools apply the two techniques described above. They have been developed as sales assistant tools and are now being adapted to the Internet. On the Internet there is no human sales assistant available to compensate for inaccuracies and lack of information. The user is going to execute the whole sales process himself, which imposes hard requirements on the quality of the sales system. The system must have a fast response time and ensure that the results are still accurate. For example, it must never be the case that the user is lead to select an alternative that is inconsistent (i.e., some of the rules become violated) with the user's earlier selections.
State-of-the-art tools have difficulties obtaining precise results and at the same time ensuring desirable response times (while dealing with complex products and allowing the system to handle many concurrent users.)
A number of patents are related to product configuration.
U.S. Pat. No. 6,115,547 discloses a product configuration comprising a specific way of caching earlier configurations improving performance of a configuration program.
U.S. Pat. No. 5,675,784 discloses a product configuration comprising a data structure (a “three tiered hierarchical data structure”) to be used for modelling products.
EP 0770239B1 discloses a product configuration comprising an expert system. This configuration method is related to rule/constraint propagation.
U.S. Pat. No. 5,206,949 discloses a product configuration comprising a database search and retrieval system.
U.S. Pat. No. 5,844,554 discloses a product configuration comprising a graphical user interface method for designing the product model.
U.S. Pat. No. 5,987,473 discloses a product configuration comprising a method for performing interactive configuration via a network.
U.S. Pat. No. 5,995,979 discloses a product configuration comprising a method for allowing a user to select an entry in a database over a network.
U.S. Pat. No. 5,996,114 discloses a product configuration comprising a method for handling the many possible configurations. This configuration method is related to Explicit Enumeration.
U.S. Pat. No. 5,745,765 discloses a product configuration comprising a method for allowing a user to select a consistent configuration.
The invention described in this patent applies a known technique symbolic model checking known from formal verification of hardware circuits to solve the computational problems inherent in developing a program for computer assisted configuration. Symbolic Model Checking is described in [K. L. McMillan Symbolic Model Checking: An Approach to the State Explosion Problem].